#-*- coding: utf-8 -*-

# # 问题描述：
# 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2
# 请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))
# 你可以假设 nums1 和 nums2 不同时为空

# 示例 1:
# nums1 = [1, 3]
# nums2 = [2]
# 中位数是 2.0

# 示例 2:
# nums1 = [1, 2]
# nums2 = [3, 4]
# 中位数是 (2 + 3)/2 = 2.5

# # 合并数组然后求中位数 时间复杂度未达到要求 O(m+n)
# # 解题过程中遇到的错误：
# # 1、判断升序的时候 使用 nums1_is_rise = nums1[1] > nums1[0];
# # 2、马虎把num2敲成nums1
# class Solution(object):
#     def findMedianSortedArrays(self, nums1, nums2):
#         """
#         :type nums1: List[int]
#         :type nums2: List[int]
#         :rtype: float
#         """
#         #判断升降序
#         nums1_is_rise = True;
#         nums2_is_rise = False;
#         if len(nums1) > 1:
#             nums1_is_rise = nums1[1] >= nums1[0];
#         if len(nums2) > 1:
#             nums2_is_rise = nums2[1] >= nums2[0];

#         #合并数组
#         nums1_index = 0;
#         nums2_index = 0;
#         if not nums1_is_rise:
#             nums1_index = len(nums1) - 1;
#         if not nums2_is_rise:
#             nums2_index = len(nums2) - 1;

#         nums_connect = [-1] * (len(nums1) + len(nums2));
#         nums_connect_index = 0;
#         while nums_connect_index < len(nums_connect):
#             nums1_is_over = nums1_index == len(nums1) if nums1_is_rise else nums1_index == -1;
#             nums2_is_over = nums2_index == len(nums2) if nums2_is_rise else nums2_index == -1;
#             if nums1_is_over:
#                 nums_connect[nums_connect_index] = nums2[nums2_index];
#                 nums_connect_index = nums_connect_index + 1;
#                 nums2_index = nums2_index + 1 if nums2_is_rise else nums2_index - 1;
#                 continue;
#             if nums2_is_over:
#                 nums_connect[nums_connect_index] = nums1[nums1_index];
#                 nums_connect_index = nums_connect_index + 1;
#                 nums1_index = nums1_index + 1 if nums1_is_rise else nums1_index - 1;
#                 continue;
#             if nums1[nums1_index] < nums2[nums2_index]:
#                 nums_connect[nums_connect_index] = nums1[nums1_index];
#                 nums1_index = nums1_index + 1 if nums1_is_rise else nums1_index - 1;
#             else:
#                 nums_connect[nums_connect_index] = nums2[nums2_index];
#                 nums2_index = nums2_index + 1 if nums2_is_rise else nums2_index - 1;
#             nums_connect_index = nums_connect_index + 1;

#         if len(nums_connect) % 2 == 0:
#             index = len(nums_connect) / 2;
#             return (nums_connect[index] + nums_connect[index-1]) / 2.0;
#         else:
#             return nums_connect[(len(nums_connect) - 1) / 2];







# 阅读官方提供的答案
# 思路主要是把2个数组分成数目相同的2堆，一堆小，一堆大，然后从中求中位数
# 具体思路分析 和 算法证明比较繁琐 请查看 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/
# 另外可查看本地文件
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """

        nums_short = nums1;
        nums_long = nums2;
        if len(nums1) > len(nums2):
            nums_short = nums2;
            nums_long = nums1;

        if len(nums_short)==0:
            if len(nums_long) % 2 == 0:
                return (nums_long[(len(nums_long) - 1) / 2]  + nums_long[len(nums_long) / 2]) / 2.0;
            else:
                return nums_long[len(nums_long) / 2];
            return;

        # 划分方式如下：
        # [0, short_split_index),[short_split_index, len(nums_short))
        # [0, long_split_index) ,[long_split_index, len(nums_long))
        # 短数组全为大数
        #                ,[.............] -> nums_short
        # [.............),[.............] -> nums_long
        # 短数组全为小数
        # [.............],                -> nums_short
        # [.............),[.............] -> nums_long
        # 一般情况
        # [......)       ,[.......]      -> nums_short
        # [.............),[.............] -> nums_long

        # 选择短的数组进行search，是为了确保对于任何合法的short_split_index计算出的long_split_index一定合法
        # len(nums_short)而不使用len(nums_short) - 1的原因是为了能够表示出所有的情况
        # eg:
        # short_split_index = 0 表示 index >= 0都属于右侧
        # short_split_index = 1 表示 index >= 1都属于右侧
        # .......
        # short_split_index = len(nums_short) - 1 表示 index == len(nums_short) - 1都属于右侧
        # 如上所示
        # 如果short_split_index的上限值是len(nums_short) - 1
        # 那么就无法表示[0, len(nums_short) - 1]所有元素都属于左侧的情况
        # 所以short_search_begin_index和short_serach_end_index的初始值的含义是左侧元素数目的取值范围
        short_search_begin_index = 0;
        short_serach_end_index = len(nums_short);

        # 选择短的数组进行search，是为了确保对于任何合法的short_split_index计算出的long_split_index一定合法
        # 这里说的合法是指数目合法，而并不一定是下标合法
        # eg:
        # short_split_index == 0是long_split_index的数目是合法的，但是long_split_index的下标是不合法的
        while short_search_begin_index <= short_serach_end_index:
            # 对半分的时候(len(nums_short) + len(nums_long) + 1)是为了确保当不能平分的时候，使左侧的元素比右侧多一个
            # short_split_index的含义是nums_short中左侧元素的数目
            # 所以short_split_index = len(nums_short)是算出来的long_split_index的数值依旧是合法的
            short_split_index = (short_search_begin_index + short_serach_end_index) / 2;
            long_split_index = (len(nums_short) + len(nums_long) + 1) / 2 - short_split_index;
            # 正确位置判定
            # 需要对0进行处理，而不需要对len(nums_short)
            # 因为0可能是第一次迭代的值，而len(nums_short)绝对是最后一次迭代到的值，因为答案是一定有的，所以当出现len(nums_short)时len(nums_short)绝对就是答案
            if short_split_index == len(nums_short):
                break;
            elif short_split_index == 0:
                if nums_long[long_split_index - 1] <= nums_short[short_split_index]:
                    break;
            elif nums_short[short_split_index - 1] <= nums_long[long_split_index] and nums_long[long_split_index - 1] <= nums_short[short_split_index]:
                break;
            # 不正确的位置
            if nums_long[long_split_index - 1] > nums_short[short_split_index]:
                short_search_begin_index = short_split_index + 1;
            else:
                short_serach_end_index = short_split_index - 1;

        if short_split_index == 0:
            left_max = nums_long[long_split_index - 1];
        elif long_split_index == 0:
            left_max = nums_short[short_split_index - 1];
        else:
            left_max = max(nums_short[short_split_index - 1], nums_long[long_split_index - 1]);

        if short_split_index == len(nums_short):
            right_min = nums_long[long_split_index];
        elif long_split_index == len(nums_long):
            right_min = nums_short[short_split_index];
        else:
            right_min = min(nums_short[short_split_index], nums_long[long_split_index]);

        if (len(nums_short) + len(nums_long)) % 2 == 0:
            #左边部分的最大值和右边部分的最小值之和的一半
            return (left_max + right_min) / 2.0;
        else:
            #左边部分的最大值
            return left_max;

# 学习到的内容：
# 首先关于问题，学习到我们可以在log(m + n)的时间复杂度上获取2个有序数列的中位数
# 其次扩展一下，如果我们要求n个数中的中位数，我们可以把它先拆分为2部分，每一部分排序然后再求中位数，这样能比原来快4倍

# 写算法时学习到的内容
# 多注意对边界条件的处理


# # 官方代码只有32行，阅读官方代码，并对自己的代码进行改机
# class Solution(object):
#     def findMedianSortedArrays(self, nums1, nums2):
#         nums_short = nums1;
#         nums_long = nums2;
#         if len(nums1) > len(nums2):
#             nums_short = nums2;
#             nums_long = nums1;

#         if len(nums_short)==0:
#             if len(nums_long) % 2 == 0:
#                 return (nums_long[(len(nums_long) - 1) / 2]  + nums_long[len(nums_long) / 2]) / 2.0;
#             else:
#                 return nums_long[len(nums_long) / 2];
#             return;

#         short_search_begin_index = 0;
#         short_serach_end_index = len(nums_short);

#         while short_search_begin_index <= short_serach_end_index:
#             short_split_index = (short_search_begin_index + short_serach_end_index) / 2;
#             long_split_index = (len(nums_short) + len(nums_long) + 1) / 2 - short_split_index;

#             if short_split_index < len(nums_short) and nums_long[long_split_index - 1] > nums_short[short_split_index]:
#                 short_search_begin_index = short_split_index + 1;
#             elif short_split_index > 0 and nums_short[short_split_index -1] > nums_long[long_split_index]:
#                 short_serach_end_index = short_split_index - 1;
#             else:
#                 break;

#         if short_split_index == 0:
#             left_max = nums_long[long_split_index - 1];
#         elif long_split_index == 0:
#             left_max = nums_short[short_split_index - 1];
#         else:
#             left_max = max(nums_short[short_split_index - 1], nums_long[long_split_index - 1]);

#         if short_split_index == len(nums_short):
#             right_min = nums_long[long_split_index];
#         elif long_split_index == len(nums_long):
#             right_min = nums_short[short_split_index];
#         else:
#             right_min = min(nums_short[short_split_index], nums_long[long_split_index]);

#         if (len(nums_short) + len(nums_long)) % 2 == 0:
#             return (left_max + right_min) / 2.0;
#         else:
#             return left_max;

# 记忆此算法的关键点
# 1、针对short的数组进行查找，这样能保证计算出的long的参数合法
# 2、[begin, end]的范围值得是数目，因而范围是[0, len]
# 3、以二分法向答案逼近，考虑不符合条件的情况，比考虑符合条件的情况简单
# 4、左右分好堆后，按照左边只有short或者左边只有long的情况求取最大最小值

t = Solution();
print t.findMedianSortedArrays([2, 2, 2], [2, 2]);